package com.demo.java.OD151_200.OD187;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【寻找路径】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/129759733
 */
public class OdMain {
    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            String line = scanner.nextLine(); // 读取一行输入
            solve(line); // 调用solve方法处理
        }
    }

    private static void solve(String line) {
        String[] split = line.split(" "); // 拆分输入的字符串
        int[] nums = new int[split.length + 1]; // 创建一个数组来存储节点值
        int minPos = 0; // 最小节点的位置

        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 最小堆
        // 填充数组并找出最小节点
        for (int i = 1; i < nums.length; ++i) {
            nums[i] = Integer.parseInt(split[i - 1]); // 解析输入值并存入数组
            if (i > 1 && nums[i] != -1) { // 如果该节点存在
                minHeap.offer(nums[i]); // 将节点加入最小堆
                if (nums[i] == minHeap.peek()) { // 如果该节点是最小节点
                    minPos = i; // 更新最小节点的位置
                }
            }
        }

        // 回溯路径
        List<Integer> way = new ArrayList<>();
        while (minPos >= 1) {
            way.add(nums[minPos]); // 将节点值添加到路径中
            minPos /= 2; // 向上回溯父节点
        }

        // 输出路径
        for (int i = way.size() - 1; i >= 0; --i) {
            System.out.print(way.get(i)); // 按从根到叶的顺序输出
            if (i != 0) { // 如果不是最后一个节点，打印空格分隔
                System.out.print(" ");
            }
        }
    }
}